package cn.handong.tool.algorithm.BFS;

import java.awt.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;


public class MyMaze {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入宽和高（9 12）：");
        int width = sc.nextInt();
        int height = sc.nextInt();
        System.out.println("迷宫的宽：" + width + "高：" + height);
        int x,y;
        // 迷宫数组创建
        int[][] mazearr = new int[2 * width + 1][2 * height + 1];//动态初始化
        // 在数组上生成迷宫
        getMaze(mazearr);
        System.out.println("生成迷宫图：");
        // 打印迷宫
        for (int i = 0; i < mazearr.length; i++) { //行
            for (int j = 0; j < mazearr[0].length; j++) {

                if (mazearr[i][j] == 1 ) {
                    System.out.print(" #");
                } else {
                    System.out.print("  ");
                }

            }
            System.out.println();
        }
        // bfs广度优先遍历 寻路
        // 1墙 2路 4已访问
        // 该数组记录父类节点
        Point[][] bookarr = new Point[2 * width + 1][2 * height + 1];
        // 创建队列
        Queue<Point> queue = new LinkedList<>();
        Point node = new Point(1, 1); // 起点
        queue.offer(node); // 起点入队
        mazearr[1][1] = 4; //起点标记为已访问
        while (!queue.isEmpty()){ // 队列为空时，结束
            node = queue.poll(); //出队
            if (node.x == mazearr.length - 2 && node.y == mazearr[0].length - 2){ //找到终点
                break;
            }else {
                x = node.x;
                y = node.y;
                if (mazearr[x-1][y] == 2){
                    queue.offer(new Point(x-1,y)); // 入队
                    mazearr[x-1][y] = 4;              // 已访问
                    bookarr[x-1][y] = new Point(x,y); //记录父节点，用来返回路径
                }
                if (mazearr[x+1][y] == 2){
                    queue.offer(new Point(x+1,y)); // 入队
                    mazearr[x+1][y] = 4;              // 已访问
                    bookarr[x+1][y] = new Point(x,y); //记录父节点，用来返回路径
                }
                if (mazearr[x][y-1] == 2){
                    queue.offer(new Point(x,y-1)); // 入队
                    mazearr[x][y-1] = 4;              // 已访问
                    bookarr[x][y-1] = new Point(x,y); //记录父节点，用来返回路径
                }
                if (mazearr[x][y+1] == 2){
                    queue.offer(new Point(x,y+1)); // 入队
                    mazearr[x][y+1] = 4;              // 已访问
                    bookarr[x][y+1] = new Point(x,y); //记录父节点，用来返回路径
                }
            }
        }
        int step = 0; //记录路径步数
        // 查找路径
        while (node.x != 1 || node.y != 1){
            node = bookarr[node.x][node.y];
            mazearr[node.x][node.y] = 5; // 5路径
            step++;
        }
        System.out.println("Bfs路径步数为："+step);
        System.out.println("Bfs路径为：");
        for (int i = 0; i < mazearr.length; i++) {
            for (int j = 0; j < mazearr[0].length; j++) {
                if ((i == 1 && j == 1) || (i == mazearr.length - 2 && j == mazearr[0].length - 2)){
                    System.out.print(" @");
                }else if (mazearr[i][j] == 5){
                    System.out.print(" >");
                }else if (mazearr[i][j] == 1){
                    System.out.print(" #");
                }else {
                    System.out.print("  ");
                }
            }
            System.out.println();
        }
    }

    private static void getMaze(int[][] mazearr){
        for (int i = 0; i < mazearr.length; i++) {
            for (int j = 0; j < mazearr[0].length; j++) {
                if (i % 2 == 0 || j % 2 == 0){
                    mazearr[i][j] = 1;
                }
            }
        }
        int x = 1, y = 1;//起点
        Point point = new Point(1, 1);
        ArrayList<Point> list = new ArrayList<>();
        mazearr[x][y] = 2; //起点设为已访问
        list = addWall(new Point(x,y),list,mazearr);
        int r ;
        while (!list.isEmpty()){
            r = (int) (Math.random()*list.size());
            x = list.get(r).x;
            y = list.get(r).y;  //墙坐标

            if (mazearr[x-1][y]==0){
                mazearr[x][y] = 2;
                mazearr[x-1][y]=2; //空格坐标
                list = addWall(new Point(x-1,y),list,mazearr);

            }
            if (mazearr[x+1][y]==0){
                mazearr[x][y] = 2;
                mazearr[x+1][y]=2;
                list = addWall(new Point(x+1,y),list,mazearr);


            }
            if (mazearr[x][y-1]==0){
                mazearr[x][y] = 2;
                mazearr[x][y-1]=2;
                list = addWall(new Point(x,y-1),list,mazearr);

            }
            if (mazearr[x][y+1]==0){
                mazearr[x][y] = 2;
                mazearr[x][y+1]=2;
                list = addWall(new Point(x,y+1),list,mazearr);


            }
            list.remove(r);
        }
    }

    private static ArrayList<Point> addWall(Point p, ArrayList<Point> list, int[][] mazearr) {
        int x = p.x;
        int y = p.y;  //路坐标
        if (0<x-2 && x-2<mazearr.length){ //上
            if(mazearr[x-2][y]==0 && mazearr[x-1][y]==1){
                // 加入邻墙
                list.add(new Point(x-1,y));
            }
        }
        if (0<x+2 && x+2<mazearr.length){ //
            if(mazearr[x+2][y]==0 && mazearr[x+1][y]==1){
                // 加入邻墙
                list.add(new Point(x+1,y));
            }
        }

        if (0<y-2 && y-2<mazearr[0].length){ //
            if(mazearr[x][y-2]==0 && mazearr[x][y-1]==1){
                // 加入邻墙
                list.add(new Point(x,y-1));
            }
        }
        if (0<y+2 && y+2<mazearr[0].length){ //
            if(mazearr[x][y+2]==0 && mazearr[x][y+1]==1){
                // 加入邻墙
                list.add(new Point(x,y+1));
            }
        }
        return list;
    }
}
